home *** CD-ROM | disk | FTP | other *** search
/ Shareware Grab Bag / Shareware Grab Bag.iso / 007 / tools.c < prev    next >
C/C++ Source or Header  |  1985-06-03  |  14KB  |  592 lines
  1. #include    "b:stdio.h"
  2. #include    "b:grep.h"
  3.  
  4. /*
  5.  * This module contains the utilities for use by the GREP
  6.  * routine to match patterns.  Routines are in alphabetical
  7.  * order.
  8.  */
  9.  
  10. int    amatch( lin , pat, boln)
  11.     char    *lin, *boln ;
  12.     TOKEN    *pat ;
  13.     {
  14.  
  15.     /*     Scans throught the pattern template looking for a match
  16.      * with lin.  Each element of lin is compared with the template
  17.      * until either a mis-match is found or the end of the tempalte
  18.      * is reached.  In teh formaer cas a zero is returned; in the
  19.      * latter, a pointer into lin ( pointing to the last character in
  20.      * in the matched pattern) is returned .
  21.      *
  22.      *         'lin'     is a pointer to the line being searched
  23.      *         'pat'    is a pointer to the template made by matchpat()
  24.      *        'boln'    is a pointer into 'lin' which points to the character
  25.      *                at the beginning of the line.
  26.      *
  27.      */
  28.  
  29.     register    char    *bocl, *rval, *strstart ;
  30.  
  31.     if( pat == 0)
  32.         return(0) ;
  33.  
  34.     strstart = lin ;
  35.  
  36.     while( pat ) {
  37.         if( pat->tok == CLOSURE && pat->next ) {
  38.  
  39.             /* Process a closure: First skip over the closure token
  40.              * to the object to be repeated
  41.              */
  42.  
  43.             pat = pat->next ;
  44.  
  45.             /* Now match as many occurances of the closure pattern as
  46.              * possible
  47.              */
  48.  
  49.             bocl = lin ;
  50.             while( *lin && omatch(&lin, pat) ) 
  51.                 ;
  52.  
  53.             /*    'lin' now points to the character that mad us fail.  Now
  54.              *  go on to process the rest of the string.  A problem here is
  55.              *    a character following the closure which could have been in
  56.              *     the closure.  For example, in the pattern '[a-z]*t', the final
  57.              *    't' would have been sucked up while in the loop.  So if the
  58.              *    match fails, we back up a notch a try to match the rest of
  59.              *    the string again, repeating the process recursively until we
  60.              *    get to the beginning of the closure.  The recursion goes
  61.              *    at most two levels deep.
  62.              */
  63.  
  64.             if(pat = pat->next) {
  65.                 while( bocl <= lin ) {
  66.                     if( rval = amatch(lin, pat, boln) ) {
  67.                         return( rval ) ;    /* success */
  68.                     }
  69.                     else 
  70.                         --lin ;
  71.                 }
  72.                 return(0) ;                    /* matched failed */
  73.             }
  74.         }
  75.         else if ( omatch( &lin, pat, boln) ) {
  76.             pat = pat->next ;
  77.             }
  78.         else {
  79.             return( 0 ) ;
  80.         }
  81.     }
  82.  
  83.     /*    Note that omatch() advances lin to point at the next character
  84.      *    to be matched; consequently, when we reach the end of the template,
  85.      *     lin will be pointing at the character following the last character
  86.      *    matched.  The exceptions are tempaltes containing only a BOl or EOL
  87.      *     token.  In these cases omatch doesn't advance.
  88.      *    
  89.      *    So, decrement lin to make it point at the end of the matched string
  90.      *    as long as this doesn't take us past the beginning of the string.
  91.      */
  92.  
  93.     return( max(strstart, --lin) ) ;
  94. }
  95.  
  96. /*---------------------------------------------------------------*/
  97. delete( ch, str )
  98.     int                ch ;
  99.     register char    *str ;
  100.     {
  101.     
  102.     /* delete the first occurance of the character from the string
  103.      * and move everything else over a notch to fill the hole
  104.      */
  105.  
  106.     ch &= 0xff ;
  107.     while( *str && *str != ch)
  108.         str++ ;
  109.     while( *str ) {
  110.         *str = *(str+1) ;
  111.         str++ ;
  112.     }
  113. }
  114.  
  115. /*--------------------------------------------------------------*/
  116. int    dodash( delim, src, dest, maxccl )
  117.     int        delim, maxccl ;
  118.     char    **src, *dest ;
  119.     {
  120.  
  121.     /*    Expand the set pointed to by *src into dest.  Stop at delim.
  122.      *     Return 0 on error or the size of the character class on success.
  123.      *    Update *src to point at delim.  A set can have on element {x} or
  124.      *     several elements ( {abcdefghijklmn} and {a-n} are equivalent).
  125.      *     Note: the dash notation is expanded as sequential numbers.  This
  126.      *     means that the set {a-Z} will contain the extra characters [\]^_ and
  127.      *    ` . The maximum number of characters is defined by maxccl
  128.      */
  129.  
  130.     register char    *dstart ;
  131.     register int    k, at_begin ;
  132.     char            *sptr, ctest ;
  133.  
  134.     dstart = dest ;
  135.     sptr = *src ;
  136.     at_begin = 1 ;
  137.  
  138.     while( *sptr && (*sptr != delim ) && (dest-dstart < maxccl)  ) {    
  139.  
  140.         if( *sptr == ESCAPE ) {            /* handle escape \ characters*/
  141.             *dest++ = esc( &sptr ) ;
  142.             sptr++ ;
  143.         }
  144.  
  145.         else if ( *sptr != '-' ) {        /* handle normal characters */
  146.             *dest++ = *sptr++ ;
  147.             }
  148.  
  149.         else if ( at_begin || *(sptr+1) == delim ) {
  150.             *dest++ = '-' ;                /* literal '-' */
  151.             }
  152.  
  153.         else if ( *(sptr-1) <= *(sptr+1) ) {
  154.             sptr++ ;
  155.             for( k = *(sptr-2) ; ++k <= *sptr ; )
  156.                 *dest++ = k ;
  157.             sptr++ ;
  158.         }
  159.  
  160.         else {
  161.             return(0) ;
  162.         }
  163.         at_begin = 0 ;
  164.     }
  165.     *dest++ = '\000' ;
  166.     *src = sptr ;
  167.  
  168.     return( dest - dstart ) ;
  169. }
  170.  
  171. /*-----------------------------------------------------------------*/
  172. int    esc(s)
  173.     char    **s ;
  174.     {
  175.     register int    rval ;
  176.  
  177.     /* Map escape sequences onto their actual ASCII values.  If no
  178.      * escape prefix is present, s is untouched and *s is returned,
  179.      * otherwise **s is advanced to point to the escaped character
  180.      * and the translated character is returned
  181.      */
  182.  
  183.     if ( **s != ESCAPE ) {
  184.         rval = **s ;
  185.     }
  186.     else {
  187.         (*s)++ ;
  188.         switch( toupper(**s) ) {
  189.             case '\000' : rval = ESCAPE ;    break ;
  190.             case 'S'    : rval = ' '    ;   break ;
  191.             case 'N'    : rval = '\n'   ;   break ;
  192.             case 'T'    : rval = '\t'   ;   break ;
  193.             case 'B'    : rval = '\b'   ;   break ;
  194.             case 'R'    : rval = '\r'   ;   break ;
  195.             default        : rval = **s    ;    break ;
  196.         }
  197.     }
  198.     return( rval) ;
  199. }
  200.  
  201. /*----------------------------------------------------------------*/
  202. TOKEN    *getpat( arg )
  203.     char    *arg ;
  204.     {
  205.  
  206.     /* Translate arg into a token string */
  207.     
  208.     return( makepat( arg, '\000' ) ) ;
  209. }
  210.  
  211. /*-----------------------------------------------------------------*/
  212. insert( ch, str )
  213.     int                ch ;
  214.     register char    *str ;
  215.     {
  216.  
  217.     /* Insert ch into string at the place pointed to by str.  Move 
  218.      * everything else over a notch
  219.      */
  220.  
  221.     register char    *bp ;
  222.  
  223.     bp = str ;
  224.     while( *str )         /* find the end of the string */
  225.         str++ ;
  226.     do {                /* move the string over a notch */
  227.         *(str+1) = *str ;
  228.         str-- ;
  229.     } while ( str >= bp ) ;
  230.     *bp = ch ;
  231. }
  232.  
  233. /*------------------------------------------------------------------*/
  234. char    *in_string( delim, str )
  235.     register int    delim ;
  236.     register char    *str ;
  237.     {
  238.  
  239.     /* return a pointer to delim if it is in the string, 0 otherwise */
  240.  
  241.     delim &= 0x7f ;
  242.     while( *str && *str != delim )
  243.         str++ ;
  244.     return( *str ? str : 0 ) ;
  245. }
  246.  
  247. /*-------------------------------------------------------------------*/
  248. int    isalphanum(c)
  249.     int    c ;
  250.     {
  251.     return( ('a' <= c && c <= 'z') ||
  252.             ('A' <= c && c <= 'Z') ||
  253.             ('0' <= c && c <= '9') ) ;
  254. }
  255.  
  256. /*--------------------------------------------------------------------*/
  257. TOKEN    *makepat( arg, delim )
  258.     char    *arg ;
  259.     int        delim ;
  260.     {
  261.  
  262.     /*    Make a pattern template from the string pointed to by arg.  Stop
  263.      *    when delim or '\000' or '\n' is found is arg.  Reurn a pointer to
  264.      *    the pattern template.
  265.      *
  266.      *    The pattern template used here is somewhat different from those
  267.      *    used in the book; each token is a structure of the form TOKEN.
  268.      *    A token consists of an identifier, a pointer to a string, a literal
  269.      *    character and a pointer to the next token.  This last is 0 if there is
  270.      *    no additional token.
  271.      *
  272.      */
  273.  
  274.     TOKEN    *head, *tail ;
  275.     TOKEN    *ntok ;
  276.     char    buf[CLS_SIZE] ;
  277.     int        error ;
  278.  
  279.     /*    Check for characters thatt aren't legal at the begiining of a token */
  280.  
  281.     if ( *arg == '\0' || *arg == delim || *arg == '\n' || *arg == CLOSURE)
  282.         return(0) ;
  283.  
  284.     error = 0 ;
  285.     head = 0 ;
  286.     tail = 0 ;
  287.     while( *arg && *arg != delim && *arg != '\n' && !error ) {
  288.         ntok = malloc ( TOKSIZE ) ;
  289.         ntok->string = &(ntok->lchar) ;
  290.         ntok->lchar = '\000' ;
  291.         ntok->next = 0 ;
  292.  
  293.         switch( *arg ) {
  294.  
  295.             case ANY :
  296.                 ntok->tok = ANY ;
  297.                 break ;
  298.             
  299.             case BOL :
  300.                 if( head == 0 )        /* this is the first symbol */
  301.                     ntok->tok = BOL ;
  302.                 else
  303.                     error = 1 ;
  304.                 break ;
  305.  
  306.             case EOL :
  307.             if( *(arg+1) == delim || *(arg+1) == '\000' || *(arg+1) == '\n' )
  308.                     ntok->tok = EOL ;
  309.                 else
  310.                     error = 1 ;
  311.                 break ;
  312.  
  313.             case CCL :
  314.                 if ( *(arg+1) == NEGATE ) {
  315.                     ntok->tok = NCCL ;
  316.                     arg += 2 ;
  317.                 }
  318.                 else {
  319.                     ntok->tok = CCL ;
  320.                     arg++ ;
  321.                 }
  322.                 error = dodash( CCLEND, &arg, buf, CLS_SIZE) ;
  323.                 if ( error != 0 ) {
  324.                     ntok->string = malloc( error ) ;
  325.                     strcpy( ntok->string, buf ) ;
  326.                     error = 0 ;
  327.                 }
  328.                 break ;
  329.  
  330.             case CLOSURE:
  331.                 if( head != 0 ) {
  332.                     switch( tail->tok ) {
  333.  
  334.                         case BOL:
  335.                         case EOL:
  336.                         case CLOSURE:
  337.                             return(0) ;
  338.                         default:
  339.                             ntok->tok = CLOSURE ;
  340.                     }
  341.                 }
  342.                 break ;
  343.  
  344.             default:
  345.                 ntok->tok = LITCHAR ;
  346.                 ntok->lchar = esc( &arg ) ;
  347.         }
  348.  
  349.  
  350.         if( error || ntok == 0 ) {
  351.             unmakepat( head ) ;
  352.             return( 0 ) ;
  353.         }
  354.         else if ( head == 0 ) {
  355.             ntok->next = 0 ;        /* this is the first node in the chain */
  356.             head = tail = ntok ;
  357.         }
  358.         else if ( ntok->tok != CLOSURE ) {
  359.             tail->next = ntok ;        /* Insert at the end of the list */
  360.             ntok->next = tail ;
  361.             tail = ntok ;
  362.         }
  363.         else if( head != tail ) {
  364.             (tail->next)->next = ntok ;    /* More than one node in the chain.    */
  365.             ntok->next = tail ;            /* Insert the CLOSURE node immediately */
  366.                                         /* in front of the tail */
  367.         }
  368.         else {
  369.             ntok->next = head ;            /* Only one node in the chain, Insert */
  370.             tail->next = ntok ;            /* node at the head of the linked list*/
  371.             head = ntok ;
  372.         }
  373.         arg++ ;
  374.     }
  375.     tail->next = 0 ;
  376.     return( head ) ;
  377. }
  378.  
  379. /*-----------------------------------------------------------------------*/
  380. char    *matchs( line, pat, ret_endp )
  381.     char    *line ;
  382.     TOKEN    *pat ;
  383.     int    ret_endp ;
  384.     {
  385.  
  386.     /*    Compares line and pattern.  Line is a character string while pat
  387.      *    is a pattern template made by getpat().  Returns:
  388.      *        (1) a 0 if no match is found
  389.      *        (2) a pointer to the last character satisfying the match if
  390.      *            ret_endp is non-zero
  391.      *        (3) A pointer to the beggining of the matched string if ret_endp
  392.      *            is non-zero
  393.      */
  394.  
  395.     char *rval, *bptr ;
  396.     bptr = line ;
  397.     while( *line ) {
  398.         if( (rval = amatch(line, pat, bptr)) == 0 ) {
  399.             line++ ;
  400.         }
  401.         else {
  402.             rval = ret_endp ? rval : line ;
  403.             break ;
  404.         }
  405.     }
  406.     return(rval) ;
  407. }
  408.  
  409. /*--------------------------------------------------------------------------*/
  410. stoupper( str )
  411.     char    *str ;
  412.     {
  413.  
  414.     /*  Map the entire string pointed to by str to upper case */
  415.     char    *rval ;
  416.  
  417.     rval = str ;
  418.     while( *str ) {
  419.         if( 'a' <= *str && *str <= 'z' )
  420.             *str -= ('a' - 'A') ;
  421.         str++ ;
  422.     }
  423. }
  424.  
  425. /*---------------------------------------------------------------------------*/
  426. int    max( x, y )
  427.     int    x, y ;
  428.     {
  429.     return( (x>y) ? x : y ) ;
  430. }
  431.  
  432. /*----------------------------------------------------------------------------*/
  433. int    omatch( linp, pat, boln)
  434.     char    **linp, *boln ;
  435.     TOKEN    *pat ;
  436.     {
  437.  
  438.     /*    Match one pattern element, pointed at by pat, with the character
  439.      *    at **linp. Return non-zero on match. Otherwise return 0. Linp is
  440.      *    advanced to skip over the matched cahracter; it is not advanced on
  441.      *    failure.  The amount of teh match is 0 for matches to null strings,
  442.      *    or 1 otherwise.  "boln" should point at the position at the position
  443.      *    that will match a BOL token.
  444.      */
  445.  
  446.     register int    advance ;
  447.  
  448.     advance = -1 ;
  449.     if( **linp ) {
  450.         switch( pat->tok ) {
  451.             case LITCHAR:
  452.                 if( **linp == pat->lchar )
  453.                     advance = 1 ;
  454.                 break ;
  455.             
  456.             case BOL:
  457.                 if( **linp == boln )
  458.                     advance = 0 ;
  459.                 break ;
  460.             
  461.             case ANY:
  462.                 if( **linp != '\n' )
  463.                     advance = 1 ;
  464.                 break ;
  465.  
  466.             case EOL:
  467.                 if( **linp == '\n' )
  468.                     advance = 0 ;
  469.                 break ;
  470.  
  471.             case CCL:
  472.                 if( in_string( **linp, pat->string) )
  473.                     advance = 1 ;
  474.                 break ;
  475.             
  476.             case NCCL:
  477.                 if( ! in_string( **linp, pat->string) )
  478.                     advance = 1 ;
  479.                 break ;
  480.             
  481.             default:
  482.                 printf("omatch: can't happen\n") ;
  483.             }
  484.     }
  485.     if( advance >= 0 )
  486.         *linp += advance ;
  487.     return( ++advance ) ;
  488. }
  489.  
  490. /*---------------------------------------------------------------------*/
  491. pr_line( ln ) 
  492.     register char    *ln ;
  493.     {
  494.     for( ; *ln ; ln++ ) {
  495.         if( (' ' <= *ln) && (*ln <= '~') )
  496.             putchar( *ln ) ;
  497.         else {
  498.             printf("\\0x%02x", *ln) ;
  499.             if( *ln == '\n' )
  500.                 putchar( '\n' ) ;
  501.         }
  502.     }
  503. }
  504.  
  505. /*--------------------------------------------------------------------*/
  506. pr_tok( head )
  507.     TOKEN    *head ;
  508.     {
  509.     register char    *str ;
  510.  
  511.     for ( ; head ; head = head->next ) {
  512.         switch( head->tok ) {
  513.             
  514.             case BOL:
  515.                 str = "BOL" ;
  516.                 break ;
  517.  
  518.             case EOL:
  519.                 str = "EOL" ;
  520.                 break ;
  521.             
  522.             case ANY:
  523.                 str = "ANY" ;
  524.                 break ;
  525.             
  526.             case LITCHAR:
  527.                 str = "LITCHAR" ;
  528.                 break ;
  529.             
  530.             case ESCAPE:
  531.                 str = "ESCAPE" ;
  532.                 break ;
  533.             
  534.             case CCL:
  535.                 str = "CCL" ;
  536.                 break ;
  537.             
  538.             case CCLEND:
  539.                 str = "CCLEND" ;
  540.                 break ;
  541.             
  542.             case NEGATE:
  543.                 str = "NEGATE" ;
  544.                 break ;
  545.             
  546.             case NCCL:
  547.                 str = "NCCL" ;
  548.                 break ;
  549.             
  550.             case CLOSURE:
  551.                 str = "CLOSURE" ;
  552.                 break ;
  553.             
  554.             default:
  555.                 str = "***** unknown *****" ;
  556.                 break ;
  557.         }
  558.         printf("%-8s at: 0x%x, ",str, head ) ;
  559.         if ( head->tok == CCL || head->tok == NCCL )
  560.             printf("string = [ %s ] =, ",head->string) ;
  561.         else if (head->tok == LITCHAR )
  562.             printf("lchar = %c, ",head->lchar) ;
  563.         printf("next = 0x%x\n", head->next) ;
  564.     }
  565.     putchar('\n') ;
  566. }
  567.  
  568. /*-----------------------------------------------------------------------*/
  569. unmakepat( head )
  570.     TOKEN    *head ;
  571.     {
  572.     register TOKEN    *old_head ;
  573.  
  574.     while( head ) {
  575.         switch (head->tok) {
  576.  
  577.             case CCL:
  578.             case NCCL:
  579.                 free(head->string) ;
  580.             default:
  581.                 old_head = head ;
  582.                 head = head->next ;
  583.                 free(old_head) ;
  584.                 break ;
  585.         }
  586.     }
  587. }
  588.  
  589.  
  590.  
  591.  
  592.